{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Sum BSTs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #two-pointers #binary-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #双指针 #二分查找 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoSumBSTs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找两棵二叉搜索树之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出两棵二叉搜索树的根节点&nbsp;<meta charset=\"UTF-8\" /><code>root1</code>&nbsp;和<meta charset=\"UTF-8\" />&nbsp;<code>root2</code>&nbsp;，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值&nbsp;<code>Target</code>。</p>\n",
    "\n",
    "<p>如果可以找到返回&nbsp;<code>True</code>，否则返回&nbsp;<code>False</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/10/ex1.png\" style=\"height: 169px; width: 369px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [2,1,4], root2 = [1,0,3], target = 5\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>2 加 3 和为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/02/10/ex2.png\" style=\"height: 290px; width: 453px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树上节点数在<meta charset=\"UTF-8\" />&nbsp;<code>[1, 5000]</code>&nbsp;范围内。<meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= Node.val, target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-sum-bsts](https://leetcode.cn/problems/two-sum-bsts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-sum-bsts](https://leetcode.cn/problems/two-sum-bsts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4]\\n[1,0,3]\\n5', '[0,-10,10]\\n[5,1,7,0,2]\\n18']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(node, arr):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left, arr)\n",
    "            arr.append(node.val)\n",
    "            dfs(node.right, arr)\n",
    "        a = []\n",
    "        b = []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        def find(arr, val):\n",
    "            index = bisect_left(arr, val)\n",
    "            if index != len(arr) and arr[index] == val:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in a:\n",
    "            if find(b, target - i):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        dic = {}\n",
    "        s = [root1]\n",
    "        while s:\n",
    "            now = s.pop()\n",
    "            dic[target-now.val] = 0\n",
    "            if now.left:\n",
    "                s.append(now.left)\n",
    "            if now.right:\n",
    "                s.append(now.right)\n",
    "        \n",
    "        s = [root2]\n",
    "        while s:\n",
    "            now = s.pop()\n",
    "            if now.val in dic:\n",
    "                return True\n",
    "            if now.left:\n",
    "                s.append(now.left)\n",
    "            if now.right:\n",
    "                s.append(now.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        it1 = TreeIterator(root1)\n",
    "        it2 = TreeIterator(root2, True)\n",
    "\n",
    "        while it1.has_next() and it2.has_next():\n",
    "            _sum = it1.peek() + it2.peek()\n",
    "            if _sum == target:\n",
    "                return True\n",
    "            elif _sum < target:\n",
    "                it1.next()\n",
    "            elif _sum > target:\n",
    "                it2.next()\n",
    "\n",
    "        return False\n",
    "\n",
    "class TreeIterator:\n",
    "    def __init__(self, root, reverse=False):\n",
    "        self.stk = []\n",
    "        self.reverse = reverse\n",
    "        if not self.reverse:\n",
    "            self.push_left_branch(root)\n",
    "        else:\n",
    "            self.push_right_branch(root)\n",
    "\n",
    "    def push_left_branch(self, root):\n",
    "        while root:\n",
    "            self.stk.append(root)\n",
    "            root = root.left\n",
    "\n",
    "    def push_right_branch(self, root):\n",
    "        while root:\n",
    "            self.stk.append(root)\n",
    "            root = root.right\n",
    "\n",
    "    def has_next(self):\n",
    "        return len(self.stk) > 0\n",
    "\n",
    "    def peek(self):\n",
    "        return self.stk[-1].val\n",
    "\n",
    "    def next(self):\n",
    "        cur = self.stk.pop()\n",
    "        if not self.reverse:\n",
    "            self.push_left_branch(cur.right)\n",
    "        else:\n",
    "            self.push_right_branch(cur.left)\n",
    "        return cur.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        stack1, stack2 = [], []\n",
    "        while True:\n",
    "            while root1:\n",
    "                stack1.append(root1)\n",
    "                root1 = root1.left\n",
    "            while root2:\n",
    "                stack2.append(root2)\n",
    "                root2 = root2.right\n",
    "            if not stack1 or not stack2:\n",
    "                return False\n",
    "            if stack1[-1].val + stack2[-1].val == target:\n",
    "                return True\n",
    "            elif stack1[-1].val + stack2[-1].val > target:\n",
    "                root2 = stack2[-1].left\n",
    "                stack2.pop()\n",
    "            else:\n",
    "                root1 = stack1[-1].right\n",
    "                stack1.pop()\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        stack1, stack2 = [], []\n",
    "\n",
    "        while True:\n",
    "            while root1:\n",
    "                stack1.append(root1)\n",
    "                root1 = root1.left\n",
    "            while root2:\n",
    "                stack2.append(root2)\n",
    "                root2 = root2.right\n",
    "\n",
    "            if not stack1 or not stack2:\n",
    "                break\n",
    "\n",
    "            node1, node2 = stack1[-1], stack2[-1]\n",
    "            curr_sum = node1.val + node2.val\n",
    "\n",
    "            if curr_sum == target:\n",
    "                return True\n",
    "            elif curr_sum < target:\n",
    "                stack1.pop()\n",
    "                root1 = node1.right\n",
    "            else:\n",
    "                stack2.pop()\n",
    "                root2 = node2.left\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            \n",
    "            stack = []\n",
    "            cur = node\n",
    "            anw = []\n",
    "            while cur or stack:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    anw.append(cur.val)\n",
    "                    cur = cur.right\n",
    "            \n",
    "            return anw\n",
    "        \n",
    "        t1 = inorder(root1)\n",
    "        t2 = inorder(root2)\n",
    "        # combine = copy.deepcopy(t1)\n",
    "        # combine.extend(t2)\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for num in t1:\n",
    "            hashmap[num].append(1)\n",
    "        for num in t2:\n",
    "            hashmap[num].append(2)\n",
    "            if target - num in hashmap and hashmap[target-num][0] != hashmap[num][0]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        def dfs(root, target):\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == target:\n",
    "                return True \n",
    "            elif root.val < target:\n",
    "                return dfs(root.right, target)\n",
    "            else:\n",
    "                return dfs(root.left, target)\n",
    "\n",
    "        return dfs(root1, target-root2.val) or self.twoSumBSTs(root1, root2.left, target) or self.twoSumBSTs(root1, root2.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        self.target = target\n",
    "        return self.subTwoSumBSTs(root1, root2, None, None, None, None)\n",
    "    \n",
    "    def subTwoSumBSTs(self, node1: Optional[TreeNode], node2: Optional[TreeNode], \n",
    "        val1_l: int, val1_h: int, val2_l: int, val2_h: int) -> bool:\n",
    "        if node1==None:\n",
    "            if (val1_l!=None and val2_l!=None and val1_l+val2_l==self.target) \\\n",
    "            or (val1_l!=None and val2_h!=None and val1_l+val2_h==self.target) \\\n",
    "            or (val1_h!=None and val2_l!=None and val1_h+val2_l==self.target) \\\n",
    "            or (val1_h!=None and val2_h!=None and val1_h+val2_h==self.target):\n",
    "                return True\n",
    "            else:\n",
    "                return self.sumValBST(val1_l, node2) or self.sumValBST(val1_h, node2)\n",
    "        if node2==None:\n",
    "            if (val1_l!=None and val2_l!=None and val1_l+val2_l==self.target) \\\n",
    "            or (val1_l!=None and val2_h!=None and val1_l+val2_h==self.target) \\\n",
    "            or (val1_h!=None and val2_l!=None and val1_h+val2_l==self.target) \\\n",
    "            or (val1_h!=None and val2_h!=None and val1_h+val2_h==self.target):\n",
    "                return True\n",
    "            else:\n",
    "                return self.sumValBST(val2_l, node1) or self.sumValBST(val2_h, node1) \n",
    "        \n",
    "        if node1.val + node2.val < self.target:\n",
    "            return self.subTwoSumBSTs(node1.right, node2.right, node1.val, val1_h, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.left, node2.right, val1_l, node1.val, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.right, node2.left, node1.val, val1_h, val2_l, node2.val)\n",
    "        elif node1.val + node2.val > self.target:\n",
    "            return self.subTwoSumBSTs(node1.left, node2.left, val1_l, node1.val, val2_l, node2.val) \\\n",
    "            or self.subTwoSumBSTs(node1.left, node2.right, val1_l, node1.val, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.right, node2.left, node1.val, val1_h, val2_l, node2.val)\n",
    "        else:\n",
    "            return True\n",
    "    \n",
    "    def sumValBST(self, val: int, node: Optional[TreeNode]) -> bool:\n",
    "        if node == None or val == None:\n",
    "            return False\n",
    "        \n",
    "        if val + node.val < self.target:\n",
    "            return self.sumValBST(val, node.right)\n",
    "        elif val + node.val > self.target:\n",
    "            return self.sumValBST(val, node.left)\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def preorder(node,res):\n",
    "            if node is None:\n",
    "                return\n",
    "            preorder(node.left, res)\n",
    "            res.append(node.val)\n",
    "            preorder(node.right, res)\n",
    "            return res\n",
    "        nums1, nums2 = preorder(root1,[]), preorder(root2,[])\n",
    "        for num in nums1:\n",
    "            index = bisect_left(nums2,target - num)\n",
    "            #print(num, index, target - num)\n",
    "            if index < len(nums2) and nums2[index] == (target - num):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.VinOrder(root1, a)\n",
    "        self.VinOrder(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        #print(a,b)\n",
    "        i = 0\n",
    "        j = bn -1\n",
    "        while i < an and j>= 0:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n",
    "    \n",
    "    def VinOrder(self, root, res:List[int]) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.VinOrder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.VinOrder(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node, res):\n",
    "        if not node:\n",
    "            return\n",
    "        self.dfs(node.left, res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right, res)\n",
    "        return res\n",
    "    \n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        res1 , res2 = self.dfs(root1, res1), self.dfs(root2, res2)\n",
    "        l1, l2, i1, i2 = len(res1), len(res2), 0, len(res2) - 1\n",
    "        while i1 < l1 and i2 > 0:\n",
    "            if res1[i1] + res2[i2] == target:\n",
    "                return True\n",
    "            elif res1[i1] + res2[i2] < target:\n",
    "                i1 += 1\n",
    "            elif res1[i1] + res2[i2] > target:\n",
    "                i2 -= 1\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        '''def search2(root2, res):\n",
    "            if not root2: return False\n",
    "            if root2.val==res: return True\n",
    "            return search2(root2.right, res) or search2(root2.left, res)\n",
    "\n",
    "\n",
    "        def dfs(root, root2):\n",
    "            if not root: return False\n",
    "            if dfs(root.right, root2):\n",
    "                return True\n",
    "\n",
    "            if search2(root2, target-root.val):\n",
    "                return True\n",
    "\n",
    "            if dfs(root.left, root2):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(root1, root2)'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def inorder(root, ls):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, ls)\n",
    "            ls.append(root.val)\n",
    "            inorder(root.right, ls)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        ls1, ls2 = [], []\n",
    "        inorder(root1, ls1)\n",
    "        inorder(root2, ls2)\n",
    "\n",
    "        p1, p2, = 0, len(ls2) - 1\n",
    "        while p1 < len(ls1) and p2 >= 0:\n",
    "            flag = ls1[p1] + ls2[p2] - target\n",
    "            if flag == 0:\n",
    "                return True\n",
    "            elif flag > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        def dfs1(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        def dfs2(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs2(root.right)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.left)\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        len1, len2 = len(res1), len(res2)\n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < len1 and p2 < len2:\n",
    "            print(res1[p1], res2[p2])\n",
    "            ans = res1[p1] + res2[p2]\n",
    "            if ans == target:\n",
    "                return True\n",
    "            elif ans < target:\n",
    "                p1 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        left_map = {}\n",
    "        right_map ={}\n",
    "        def dfs1(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            dfs1(root.right)\n",
    "            left_map[root.val] = 0\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "            right_map[root.val] = 0\n",
    "\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "\n",
    "        for key in left_map.keys():\n",
    "            if target - key in right_map.keys():\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        left_map = {}\n",
    "        right_map ={}\n",
    "        def dfs1(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            dfs1(root.right)\n",
    "            left_map[root.val] = 0\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "            right_map[root.val] = 0\n",
    "\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "\n",
    "        for key in left_map.keys():\n",
    "            if target - key in right_map.keys():\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def preo2(n, v):\n",
    "            if n.val == v: return True\n",
    "            if n.val > v and n.left:\n",
    "                return preo2(n.left, v)\n",
    "            if n.val < v and n.right:\n",
    "                return preo2(n.right, v)\n",
    "            return False\n",
    "\n",
    "        def preo1(n):\n",
    "            if preo2(root2, target-n.val): return True\n",
    "\n",
    "            if n.left:\n",
    "                if preo1(n.left): return True\n",
    "\n",
    "            if n.right:\n",
    "                if preo1(n.right): return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return preo1(root1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        arr1, arr2 = [], []\n",
    "        def dfs(node: Optional[TreeNode], arr: list[int]):\n",
    "            if node:\n",
    "                dfs(node.left, arr)\n",
    "                arr.append(node.val)\n",
    "                dfs(node.right, arr)\n",
    "\n",
    "        dfs(root1, arr1)\n",
    "        dfs(root2, arr2)\n",
    "\n",
    "        n, m = len(arr1), len(arr2)\n",
    "        i, j = 0, m - 1\n",
    "\n",
    "        while i < n and j >= 0:\n",
    "            res = arr1[i] + arr2[j]\n",
    "            if res == target:\n",
    "                return True\n",
    "            elif res > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        pre2=[]\n",
    "        #中序遍历\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                dfs(x.left)\n",
    "                pre2.append(x.val)\n",
    "                dfs(x.right)\n",
    "        dfs(root1)\n",
    "        pre1=pre2.copy()\n",
    "        pre2.clear()\n",
    "        dfs(root2)\n",
    "        #双指针搜索即可\n",
    "        i,j=0,len(pre2)-1\n",
    "        while i<len(pre1) and j>=0:\n",
    "            cur=pre1[i]+pre2[j]\n",
    "            if cur<target:\n",
    "                i+=1\n",
    "            elif cur>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.VinOrder(root1, a)\n",
    "        self.VinOrder(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        #print(a,b)\n",
    "        i = 0\n",
    "        j = bn -1\n",
    "        while i < an and j>= 0:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n",
    "    \n",
    "    def VinOrder(self, root, res:List[int]) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.VinOrder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.VinOrder(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def is_val_in_tree(self, root, val):\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == val:\n",
    "            return True\n",
    "        elif root.val < val:\n",
    "            return self.is_val_in_tree(root.right, val)\n",
    "        elif root.val > val:\n",
    "            return self.is_val_in_tree(root.left, val)\n",
    "\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        if not root1:\n",
    "            return False\n",
    "        return self.is_val_in_tree(root2, target - root1.val) or self.twoSumBSTs(root1.left, root2, target) or self.twoSumBSTs(root1.right, root2, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        def listtree(root,l):\n",
    "            if root:\n",
    "                l.append(root.val)\n",
    "                if root.left:\n",
    "                    l.append(root.left.val)\n",
    "                    listtree(root.left,l)\n",
    "                if root.right:\n",
    "                    l.append(root.right.val)\n",
    "                    listtree(root.right,l)\n",
    "                return l\n",
    "            else:\n",
    "                return l\n",
    "        l1 = listtree(root1,[])\n",
    "        l2 = listtree(root2,[])\n",
    "        for i in l1:\n",
    "            if target-i in l2:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        def dfs1(root):\n",
    "            if not root: return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if not root: return\n",
    "            dfs2(root.left)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        for x in res1:\n",
    "            for y in res2:\n",
    "                if x + y == target: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(node,res):\n",
    "            if node is None:\n",
    "                return\n",
    "            inorder(node.left, res)\n",
    "            res.append(node.val)\n",
    "            inorder(node.right, res)\n",
    "            return res\n",
    "        nums1, nums2 = inorder(root1,[]), inorder(root2,[])\n",
    "        for num in nums1:\n",
    "            index = bisect_left(nums2,target - num)\n",
    "            if index < len(nums2) and nums2[index] == (target - num):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(node: TreeNode, res: List[int]):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left,  res)\n",
    "            res.append(node.val)\n",
    "            dfs(node.right, res)\n",
    "\n",
    "        a, b = [], []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        m, n = len(a), len(b)\n",
    "\n",
    "        i, j = 0, n -1 \n",
    "        while i < m and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1  \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        # 遍历两颗数，把值换成列表\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "\n",
    "        def dfs(root,l):\n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            left = dfs(root.left,l)\n",
    "            l.append(root.val)\n",
    "            right = dfs(root.right,l)\n",
    "\n",
    "            return root.val\n",
    "\n",
    "        dfs(root1,l1)\n",
    "        dfs(root2,l2)\n",
    "        # print(l1)\n",
    "        # print(l2)\n",
    "\n",
    "        s2 = set(l2)\n",
    "        for a in l1:\n",
    "            if target - a in s2:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        pre2=[]\n",
    "        #中序遍历\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                dfs(x.left)\n",
    "                pre2.append(x.val)\n",
    "                dfs(x.right)\n",
    "        dfs(root1)\n",
    "        pre1=pre2.copy()\n",
    "        pre2.clear()\n",
    "        dfs(root2)\n",
    "        #双指针搜索即可\n",
    "        i,j=0,len(pre2)-1\n",
    "        while i<len(pre1) and j>=0:\n",
    "            cur=pre1[i]+pre2[j]\n",
    "            if cur<target:\n",
    "                i+=1\n",
    "            elif cur>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        def search2(root2, res):\n",
    "            if not root2: return False\n",
    "            if root2.val==res: return True\n",
    "            return search2(root2.right, res) or search2(root2.left, res)\n",
    "\n",
    "\n",
    "        def dfs(root, root2):\n",
    "            if not root: return False\n",
    "            if dfs(root.right, root2):\n",
    "                return True\n",
    "\n",
    "            if search2(root2, target-root.val):\n",
    "                return True\n",
    "\n",
    "            if dfs(root.left, root2):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(root1, root2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        tree1 = []\n",
    "        tree2 = []\n",
    "        def inorder(root: Optional[TreeNode], idx: int):\n",
    "            nonlocal tree1\n",
    "            nonlocal tree2\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, idx)\n",
    "            if idx == 1:\n",
    "                tree1.append(root.val)\n",
    "            else:\n",
    "                tree2.append(root.val)\n",
    "            inorder(root.right, idx)\n",
    "        inorder(root1, 1)\n",
    "        inorder(root2, 2)\n",
    "\n",
    "        left = 0\n",
    "        right = len(tree2)-1\n",
    "        while left < len(tree1) and right >= 0:\n",
    "            tmp = tree1[left]+tree2[right]\n",
    "            if target == tmp:\n",
    "                return True\n",
    "            elif tmp < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.dfs_LNR(root1, a)\n",
    "        self.dfs_LNR(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        ######## 贪心，双指针，从两边向中间夹逼\n",
    "        i = 0\n",
    "        j = bn -1 \n",
    "        while i < an and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1  \n",
    "        return False\n",
    "    ############ 二叉树 中序遍历 ############\n",
    "    def dfs_LNR(self, rt: TreeNode, res: List[int]) -> None:\n",
    "        if rt == None:\n",
    "            return\n",
    "        self.dfs_LNR(rt.left, res)\n",
    "        res.append(rt.val)\n",
    "        self.dfs_LNR(rt.right, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(root, res):\n",
    "            if not root: return None\n",
    "            dfs(root.left, res)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right, res)\n",
    "\n",
    "        a, b = [], []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        \n",
    "        an, bn = len(a), len(b)\n",
    "        i, j = 0, bn - 1\n",
    "        while i < an and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(node, arr):\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left, arr)\n",
    "            arr.append(node.val)\n",
    "            inorder(node.right, arr)\n",
    "\n",
    "        arr1, arr2 = [], []\n",
    "        inorder(root1, arr1)\n",
    "        inorder(root2, arr2)\n",
    "    \n",
    "        i, j = 0, len(arr2) - 1\n",
    "    \n",
    "        while i < len(arr1) and j >= 0:\n",
    "            if arr1[i] + arr2[j] == target:\n",
    "                return True\n",
    "            elif arr1[i] + arr2[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "    \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self,node,li):\n",
    "        if node == None:\n",
    "            return \n",
    "        self.inorder(node.left,li) \n",
    "        li.append(node.val) \n",
    "        self.inorder(node.right,li)\n",
    "        return li\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        li_1,li_2 = [],[]\n",
    "        self.inorder(root1,li_1)\n",
    "        self.inorder(root2,li_2)\n",
    "        p1,p2,len1 =0,len(li_2)-1,len(li_1)\n",
    "        while p1 < len1 and p2 >= 0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self,node,li):\n",
    "        if node == None:\n",
    "            return \n",
    "        self.inorder(node.left,li) \n",
    "        li.append(node.val) \n",
    "        self.inorder(node.right,li)\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        li_1,li_2 = [],[]\n",
    "        self.inorder(root1,li_1)\n",
    "        self.inorder(root2,li_2)\n",
    "        p1,p2,len1 =0,len(li_2)-1,len(li_1)\n",
    "        while p1 < len1 and p2 >= 0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(root, order):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, order)\n",
    "            order.append(root.val)\n",
    "            inorder(root.right, order)\n",
    "        \n",
    "        order1, order2 = [], []\n",
    "        inorder(root1, order1)\n",
    "        inorder(root2, order2)\n",
    "\n",
    "        i, j = 0, len(order2) - 1\n",
    "        while i < len(order1) and j >= 0:\n",
    "            if order1[i] + order2[j] == target:\n",
    "                return True\n",
    "            elif order1[i] + order2[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\r\n",
    "        a, b = [], []\r\n",
    "        self.dfs_LNR(root1, a)\r\n",
    "        self.dfs_LNR(root2, b)\r\n",
    "        an, bn = len(a), len(b)\r\n",
    "        ######## 贪心，双指针，从两边向中间夹逼\r\n",
    "        i = 0\r\n",
    "        j = bn -1 \r\n",
    "        while i < an and 0 <= j:\r\n",
    "            if a[i] + b[j] == target:\r\n",
    "                return True\r\n",
    "            elif a[i] + b[j] < target:\r\n",
    "                i += 1\r\n",
    "            else:\r\n",
    "                j -= 1  \r\n",
    "        return False\r\n",
    "    ############ 二叉树 中序遍历 ############\r\n",
    "    def dfs_LNR(self, rt: TreeNode, res: List[int]) -> None:\r\n",
    "        if rt == None:\r\n",
    "            return\r\n",
    "        self.dfs_LNR(rt.left, res)\r\n",
    "        res.append(rt.val)\r\n",
    "        self.dfs_LNR(rt.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def searchValue(root: Optional[TreeNode], value: int) -> bool:\n",
    "            if root == None:\n",
    "                return False\n",
    "            if root.val == value:\n",
    "                return True\n",
    "            if root.val > value:\n",
    "                return searchValue(root.left, value)\n",
    "            else:\n",
    "                return searchValue(root.right, value)\n",
    "            return False\n",
    "\n",
    "        def searchNode(root1, root2, target) -> bool:\n",
    "            if root1 == None:\n",
    "                return False\n",
    "            return searchValue(root2, target - root1.val) or searchNode(root1.left, root2, target) or searchNode(root1.right, root2, target)\n",
    "        \n",
    "        return searchNode(root1, root2, target)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def checkPair(node, target2):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == target2:\n",
    "                return True\n",
    "            if node.val < target2:\n",
    "                return checkPair(node.right, target2)\n",
    "            else:\n",
    "                return checkPair(node.left, target2)\n",
    "\n",
    "        def inOrder(root1, root2, target):\n",
    "            if not root1:\n",
    "                return False\n",
    "            \n",
    "            if checkPair(root2, target - root1.val):\n",
    "                return True\n",
    "\n",
    "            return inOrder(root1.left, root2, target) or inOrder(root1.right, root2, target)\n",
    "\n",
    "        return inOrder(root1, root2, target)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        # 将两个 BST 转化成两个有序数组\n",
    "        arr1 = self.traverse(root1)\n",
    "        arr2 = self.traverse(root2)\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        # 对有序数组执行两数之和问题的算法逻辑\n",
    "        i, j = 0, n-1\n",
    "        while i < m and j >= 0:\n",
    "            sum = arr1[i] + arr2[j]\n",
    "            if sum < target:\n",
    "                # 让和大一些\n",
    "                i += 1\n",
    "            elif sum > target:\n",
    "                # 让和小一些\n",
    "                j -= 1\n",
    "            else:\n",
    "                # 找到和 target\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    # 返回中序遍历结果\n",
    "    def traverse(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        res += self.traverse(root.left)\n",
    "        res.append(root.val)\n",
    "        res += self.traverse(root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(root: Optional[TreeNode], i: int):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left, i)\n",
    "            nums[i].append(root.val)\n",
    "            dfs(root.right, i)\n",
    "\n",
    "        nums = [[], []]\n",
    "        dfs(root1, 0)\n",
    "        dfs(root2, 1)\n",
    "        i, j = 0, len(nums[1]) - 1\n",
    "        while i < len(nums[0]) and ~j:\n",
    "            x = nums[0][i] + nums[1][j]\n",
    "            if x == target:\n",
    "                return True\n",
    "            if x < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        ans = False\n",
    "        \n",
    "        pre = set()\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            lst1.append(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return \n",
    "        \n",
    "        lst1 = []\n",
    "        dfs(root1)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            lst2.append(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return\n",
    "\n",
    "        lst2 = []\n",
    "        dfs(root2)\n",
    "        pre = set(lst1)\n",
    "        for num in lst2:\n",
    "            if target-num in pre:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        # 用于存储第一棵树节点值的集合\n",
    "        values = set()\n",
    "        \n",
    "        # 从第一棵树中遍历所有节点并存入集合\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return\n",
    "            values.add(node.val)\n",
    "            traverse(node.left)\n",
    "            traverse(node.right)\n",
    "        \n",
    "        traverse(root1)\n",
    "        \n",
    "        # 用于检查第二棵树中是否有匹配的节点值\n",
    "        def check(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            complement = target - node.val\n",
    "            if complement in values:\n",
    "                return True\n",
    "            return check(node.left) or check(node.right)\n",
    "        \n",
    "        return check(root2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        self.ret = False\n",
    "        def visit(root1):\n",
    "            if not root1:\n",
    "                return\n",
    "            self.ret = self.ret or search(root2, target-root1.val)\n",
    "            if self.ret:\n",
    "                return\n",
    "            visit(root1.left)\n",
    "            visit(root1.right)\n",
    "\n",
    "        def search(root2, val):\n",
    "            if not root2:\n",
    "                return False\n",
    "            \n",
    "            if root2.val == val:\n",
    "                return True\n",
    "            \n",
    "            elif root2.val > val:\n",
    "                return search(root2.left, val)\n",
    "            else:\n",
    "                return search(root2.right, val)\n",
    "            \n",
    "\n",
    "        visit(root1)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        def dfs1(root):\n",
    "            if not root: return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if not root: return\n",
    "            dfs2(root.left)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        res1 = list(set(res1))\n",
    "        res2 = list(set(res2))\n",
    "        for x in res1:\n",
    "            for y in res2:\n",
    "                if x + y == target: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        self.dfs(root1, set1, target)\n",
    "        self.dfs(root2, set2, target)\n",
    "        \n",
    "        for n in set1:\n",
    "            if (target - n) in set2:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self, node, s, target):\n",
    "        if node.left:\n",
    "            self.dfs(node.left, s, target)\n",
    "        s.add(node.val)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, s, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        line=set([])\n",
    "\n",
    "        def method(node):\n",
    "            nonlocal line\n",
    "            if not node:\n",
    "                return\n",
    "            else:\n",
    "                method(node.left)\n",
    "                line.add(node.val)\n",
    "                method(node.right)\n",
    "\n",
    "        def method_1(node):\n",
    "            nonlocal line\n",
    "            nonlocal target\n",
    "            if node==None:\n",
    "                return False\n",
    "            else:\n",
    "                left=method_1(node.left)\n",
    "                result=False\n",
    "                if (target-node.val) in line:\n",
    "                    result=True\n",
    "                right=method_1(node.right)\n",
    "\n",
    "                return (left or result or right)\n",
    "\n",
    "        method(root1)\n",
    "        return method_1(root2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        m = set()\n",
    "        couple = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "\n",
    "            if target - root.val in couple:\n",
    "                return True\n",
    "\n",
    "            m.add(root.val)\n",
    "            return dfs(root.left) or dfs(root.right)\n",
    "\n",
    "        dfs(root1)\n",
    "        couple = m\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def find(root, target):\n",
    "            if root == None:\n",
    "                return False\n",
    "            if root.val == target:\n",
    "                return True\n",
    "            elif root.val > target:\n",
    "                return find(root.left, target)\n",
    "            else:\n",
    "                return find(root.right, target)\n",
    "        \n",
    "        if root1 == None or root2 == None:\n",
    "            return False\n",
    "        return find(root2, target - root1.val) or self.twoSumBSTs(root1.left, root2, target) or self.twoSumBSTs(root1.right, root2, target)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
